1. Field of the Invention
The present invention generally relates to electronic circuits and, more specifically, to the protection of data contained in an integrated circuit against an extraction thereof, after fault injections into the electronic circuit operation. The present invention more specifically relates to the protection of modular exponentiation algorithms. Such algorithms are used, for example, in smart cards or secure components for ciphering or signing data by means of a secret quantity internal to the chip.
2. Discussion of the Related Art
FIG. 1 very schematically shows in the form of blocks an example of a simplified architecture of an integrated circuit 1, for example, of a smart card, of the type to which the present invention applies. Circuit 1 comprises a central processing unit 11 (CPU) associated with one or several memories 12 (MEM) among which generally at least one element of non-volatile storage of a secret quantity (for example, a confidential code), and an input/output circuit 13 (I/O) enabling data exchange with the outside of circuit 1. The different elements communicate over one or several data, address, and control buses 14. Most often, several memories 12 among which at least one RAM and one non-volatile memory are provided in the circuit.
Among the possible attacks performed by persons attempting to fraudulently obtain confidential data from chip 1, the present invention applies to so-called differential fault analysis attacks (DFA) which comprises the analysis of the result of a disturbance of the operation of component 1, for example, by means of radiation (laser, infrared, X-rays, etc.) or by other means (for example, by acting on the component supply).
Some integrated circuits comprise software tools for detecting such disturbances by checking whether a program has correctly executed. For example, the same instructions are executed twice and it is checked that they lead to the same result, or a signature calculation is performed on data extracted from the memory. In case of a fraud attempt detection, the component is generally blocked, that is, it does not provide the required result.
The data provided (output) by the component on its input/output pads are exploited by the hacker, either by their simple existence indicating the absence of a blocking, or by their content, to discover secret elements of the chip (algorithm, secret key, etc.).
In many algorithms handling digital data of which it is considered that they must not be readably extracted from circuit 1, one or several modular exponentiation operations are performed, which use multiplication operators. Such is the case, for example, for so-called DSA, RSA, and Diffie-Hellman algorithms.
FIG. 2 shows, in the form of a simplified timing diagram, a conventional example of a modular exponentiation calculation, modulo a number P over n bits, comprising, based on a message over several bits M and on a secret quantity or key d over at most n bits, the calculating of the following result:Z0=Md mod P (block 20).
To perform this calculation, it is necessary to pass through intermediary results calculated by successive multiplications. It is spoken of a square-multiply method. Such intermediary results are contained in one or several registers.
For example, a quantity Zn contained in a first register noted Z as being equal to unity (block 21, Zn=1) is initialized. Register Z will contain, at the end of an algorithm, final result Z0. A counter i is then initialized as being equal to n−1 (block 22). The index of counter i corresponds to the successive ranks of the n bits of secret quantity d, which may be written as:
  d  =            ∑              i        =        0                    n        -        1              ⁢                  d        i            ⁢                        2          i                .            
The initialization of index counter i amounts to executing a loop calculation down to i=0 (block 23), at each iteration of which successive multiplications will be performed according to the state of current bit di of quantity d.
In a first step (block 24) of this loop, an intermediary result Ri is calculated by squaring up (multiplication by itself), modulo P, the content of result register Z. Intermediary result Ri=(Zi+1)2 mod P is, in practice, stored in a register noted R.
Then (block 25), the result of this calculation is multiplied, modulo P, by message M. The result Si=Ri*M mod P of this second multiplication is stored in another register noted S.
A test (block 26, di=1?) of the state of the current bit of quantity d (the exponent of the exponentiation) is then performed. If this state is 0 (output N of block 26), the content of register Z takes value Ri (block 27). If bit di is at state 1, register Z takes value Si (block 27′). This amounts not to taking into account the calculation step of block 25 in the case where the current bit of the key is state 0.
As long as the loop has not ended (output N of block 23), counter i is decremented (block 28, i=i−1) and it is returned to the input of block 24.
At the end of the loop (output Y of block 23), register Z contains quantity Z0.
In fact, quantity Si is calculated even if it is not used for the key bits at state 0, to mask the algorithm execution against possible attacks by power analysis (SPA) of the integrated circuit by using the multiplier twice per loop, whatever the state of the current bit of secret quantity d.
A disadvantage however is that this makes the algorithm execution more sensitive to fault injection attacks. Indeed, if the execution of the calculation is disturbed after the step of block 24 while the current bit of quantity d is equal to 0, this disturbance does not modify the intermediary result Zi that must be output since the operation performed by the multiplier (block 25) is not exploited. However, if the disturbance occurs while the current bit of quantity d is at state 1, this will modify this intermediary result.
When the mechanism of protection against fault injections calculates the signature of the intermediary result, or executes the calculation a second time, it only detects a fraud attempt if the disturbance has occurred on an iteration of index i at state 1. Accordingly, this mechanism will provide final result Z0 of the calculation if the disturbance has occurred during the processing corresponding to a bit of the secret quantity at state 0. A repeating of the disturbance at different times (in different iterations) on successive executions enables the hacker to determine secret quantity d by merely observing whether the component provides a result (bit at state 0) or not (bit at state 1).